Content Addressable Memory (CAM) devices are used in applications requiring matching operation on bit patterns, such as table lookup applications used by routing and switching systems in computer network applications. Typically, CAM devices provide for the direct comparison of stored data entries with a supplied value to be compared, called a comparand, in a single access. In contrast, when using conventional Random Access Memory (RAM) for the same search operation, stored data entries are compared by supplying the address of each of the stored data entries to the RAM device, retrieving each of the data entries stored at each of the addresses, and passing the data to an arithmetic logic unit (ALU), where it is then compared to the comparand. CAM devices, on the other hand, allow the comparand to be directly compared with all the stored data entries simultaneously, and any stored data entries matching the input entry generate a match signal. More specifically, each bit position of the comparand is compared with the corresponding bit positions of data entries stored in the CAM device. A priority encoder in the CAM device identifies which matching data entry is output first in the case of multiple matching data entries, with this data entry being termed the highest priority match, as will be explained later in this document.
FIG. 1 shows a conventional CAM device 100. The CAM device 100 is directed by control logic 104, which can conventionally write or retrieve data from the CAM array 108 by accessing an address decoder 112 through an address bus 116. Data to be conventionally written to or retrieved from the CAM array 108 are provided to input/output (I/O) buffers 120, which receive and supply data through a system bus 124. The control logic 104 directs the I/O buffers 120 through a control bus 128, and data is passed between the I/O buffers 120 and the CAM array 108 through a data bus 132. The CAM device may be operated as a conventional random access memory device using just these functional elements to write and retrieve data from the CAM array 108 by the control logic 104 specifying address information to the CAM array 108 through the data bus 132.
The primary differentiator between conventional random access memory (RAM) devices and CAM devices is the ability of CAM devices to perform search or matching operations in a deterministic time period as previously described, regardless of the number of data entries stored in the CAM array. Instead of the control logic 104 directing data access to the CAM array 108 through the address decoder 112, a comparand can be moved to the Comparand Register 136, and the control logic 104 then directs the CAM array 108 to compare all data entries to the data in the Comparand Register 136. All matching data entries are prioritized by the Priority Encoder 140, which determines which matching entry is the highest priority match.
An additional component of the CAM device 100 is the Mask Register 144. This is a global mask register in that it applies equally to all data entries in the CAM array 108 per compare operation. The Mask Register 144 holds a data mask which is used to identify which bits in the data entries stored in the CAM array 108 are considered significant, and thus compared to the same bit locations in the Comparand Register 136. For example, if the bit width of the data stored in the CAM array 108 is less than the native bit width of the CAM array 108, the Mask Register 144 is invoked to include only those bits significant to the application in the compare operation. In the case of multiple data entries matching the data in the comparand register 136, the Priority Encoder 140 determines which entry is output first. In a typical CAM device 108, the Priority Encoder 140 selects the matching entry with the lowest physical address as the highest priority match. Note that typical CAM devices may have several global mask registers; each invoked for a different compare, write or read operation, and only invoked one at a time.
The CAM device 100 heretofore described is termed a binary CAM device because the matching operations for each bit across the CAM array 108, aside from those bits indicated as not significant by the mask stored in the mask register 144, will yields one of two states: match or no match. This is often called an exact match, as all non-globally masked bits of the stored entry must match the data in the comparand register 136 before the entry will indicate a match.
A ternary CAM device allows for matching operations which will yield, for each bit across its CAM array, one of three states: match, no match, or “don't care”. This third, don't care state is supported by each entry in the CAM array having its own individual, or local mask. This allows a third state to be specified individually for each bit of each data entry in the ternary CAM array 200, as shown in FIG. 2A. For each data entry 204 in the data portion 208 of the ternary CAM array 200, shown arranged from a low address 0 to a high address N, there is an associated mask 212 in the mask portion 216 of the ternary CAM array 200.
FIG. 2B shows a four-bit example of a ternary CAM array 250, and how the entries in the mask portion 254 affect the compare operation for each data entry in the data portion 258 for an example comparand of “1000”. Entries in the mask portion 254 specify a one for each bit that is significant in the compare operation, and a zero for each bit that is not significant, which forces a match for that bit location. In a compare operation with the comparand value of 1000, combining the data entries with their local masks, there are three matching entries and two no match entries in the ternary CAM array 250. Starting at the low address data entry 1001 at address 0 with the mask value of 1111, there is a no match condition. Although the first three most significant bits match, the mask of 1111 makes all the bits significant in the comparison, and the least significant bit does not match. The next data entry at address 1 contains the value 1000, and is a perfect or exact match. The corresponding mask value is 1111, making all of the data bits significant for the compare operation, so the data value needs to match the comparand value exactly to indicate a match.
By contrast, the data entry at address 2, with a value of 1011, when combined with the data mask value of 1100, will yield a match with the value of 1000 in the comparand because only the two most significant bits are compared, and the two least significant bits are a forced match. Similarly, the data value in address three of 1110, when combined with a mask value of 1100 will yield a no match with the value of 1000 in the comparand because the second most significant bit of the data does not match, and the mask value indicates this bit position as significant. Finally, at address N., the data value of 1111, when combined with the mask value of 1000 yields a match with the value of 1000 in the comparand because only the most significant bit is being compared, and they match.
The priority encoders employed in typical ternary CAM devices will resolve multiple matches by returning the matching location with the lowest physical address first. In the previous example, where addresses 1, 2, and N matched, the ternary CAM will respond with the location address 1 as the highest priority match. In applications, this requires that the data stored in the ternary CAM array be ordered by the value of the mask, with higher priority values having lower physical addresses within the ternary CAM array. In applications where the mask may have interleaved ones and zeros, the designer must decide what determines priority, and sort the data appropriately before storing in the ternary CAM array. It is important to note that all data entries with a common mask value will comprise a block of data values within the ternary CAM array when sorted by mask value. It is not necessary to further sort the data entries within each block
For most computer networking applications, the networking protocols specify the priority of multiple matching entries by the value of the mask. These protocols simplify the issue of determining priority and sorting by defining valid mask values that do not allow interleaved ones and zeros in the mask, and always include some minimum number of bits starting with the most significant data bit. This masking technique is often referred to as the network mask, or net mask.
In the previous example of FIG. 2B, the best match is the location with the longest string of ones in the mask, and having matching data in the significant bit positions. The ultimate match is an exact match with a mask value of all ones, as in address 1 of FIG. 2B. If address 1 was empty, so there would not be an exact match, the best match would be at address 2 because two most significant bits are being compared as opposed to one significant bit in address N, even though both locations would register a match. Note that in FIG. 2B, the mask value in address 3 would be an illegal net mask because it contains interleaved ones and zeros.
A typical networking application is a router. A network message received by a router might be targeted to all devices serviced by a second router connected to the first router. The devices connected to the second router have thirty-two bit addresses with the first twenty-four bits being identical. Because the message is directed to all the devices serviced by the second router, the first router is only concerned with identifying packets destined for the second router, regardless of where the second router sends the packets. The first router could keep a copy of all the network addresses of all of the devices connected to the second router, but that is an inefficient use of memory space within the first router. What the routing protocols allow is for the first router to represent all of the devices serviced by the second router with a single entry in its routing table. The entry would be stored with the value of the twenty-four identical network address bits in the most significant bits of the thirty-two bit address space, and zeros in the least significant eight bits. The corresponding mask value would be all ones in the first twenty-four bit positions, and zeros in the remaining eight bit positions. Any incoming packet to the first router with a destination address having the most significant twenty-four bits matching this entry will be forwarded to the second router, regardless of the value in the least significant eight bits.
In reality, a network router is connected to several other routers, which in turn, are connected to yet more routers, as well as end devices such as personal computers and servers. Each router connected to the first router may have one or more blocks of addresses that can be represented with one entry in the routing table of the first router, but with differing numbers of common significant bits. This means that the first router will have a variety of different net masks within its routing table; from a mask value of all ones for exact matches for end devices connected directly to this router, to a mask with few ones. These entries need to be sorted by net mask length, with the longest net mask entries at the lowest physical addresses within the CAM device, which takes processing power and time. The network space tends to be very dynamic, so this table may need to be resorted frequently, again taking processing power and time, potentially causing the ternary CAM device to not be available for a search operation when it is needed.
In conventional ternary CAM devices, gaps or empty entries are left in each net mask block of entries. This allows routers to update the routing table by inserting a new entry in an available empty location within the correct block without having to re-sort the entire table each time a new entry is inserted. Although this improves entry insertion time, it clearly wastes available resources by reserving ternary CAM array space for possible future use.
Another concern with conventional ternary CAM design is that the presentation of a comparand for a priority matching operation necessitates a search of the entire ternary CAM array. The switching of many logic gates necessary for this operation is appreciable. Some comparands might be seeking to retrieve only data entries which refer to a common table to which multiple devices might be assigned. Typically, this table information is included in each data entry assigned to the common table. Incorporating the table identifier within the address represented in the data entry consumes additional bits within the data space. Moreover, because the data entries themselves must be searched to identify data entries included in the table, a full search of the entire CAM array must be made even if only addresses are assigned to a single table are needed. Finally, some conventional CAM arrays provide for address spaces much wider than conventional IPv4 32-bit addresses, and allow for data words in excess of 144 bits in width. These devices allow for the segmentation of the native data word width of the CAM device into half-words and quarter-words when addresses short of the maximum word width are being used. Even when these words are empty or partially empty, a priority matching operation still will necessarily involve a search of the entire CAM array.
What is desired is a way to avoid having to use and occupy system resources in sorting and resorting data entries to support conventional priority matching protocols. What also is desired is a way to eliminate searching an entire ternary CAM array when the comparand seeks information, such as addresses assigned to a single, common table, or when only some of the word width in an extended width ternary CAM is used.